package 热题100.子串.滑动窗口最大值_239_困难;
/*
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值 。

示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]

示例 2：
输入：nums = [1], k = 1
输出：[1]

思路：
    单调队列：
        单调性：队列中的元素要么是递增的，要么是递减的。
        动态性：随着新元素的加入和旧元素的移除，队列中的元素会不断变化，但始终保持单调性。
        双端队列：通常使用双端队列（deque）实现，因为它允许在两端高效地插入和删除元素。
    本题维护这个单调队列就行，
    添加值阶段：
        在加入队列的时候，比较将要加进来元素下标对应的数组值 与 队尾下标对应的数组 大小
    如果前者大，那么就相当于滑动窗口中的下标i，j，此时 下标j > 下标i 且 nums[j] > nums[i]，这样i就能去掉了，因为在滑动窗口内有i一定有j
    并且值也是j大，那i就必不可能是滑动窗口最大值，就能去掉了，直到队列中没有元素，或者新元素小于当前队尾，然后将新元素加进去。
    获取最大值阶段：
        在判断滑动窗口的最大值的时候，先判断队首在不在滑动窗口中，如果在则最大值就是它，如果不在就将队首移除（如果出现数组本身就是递减的，那么在添加
    值的阶段就不会去掉元素，这样单调队列肯定是比滑动窗口的范围大的，所以要比较值是否在滑动窗口的范围内再赋值给最大值）
    这个单调队列和排序的队列区别在于，以递增数组为例，单调队列只维护当前位置以及之前的单调关系，会出现后面位置的值小于当前位置的最大值的情况，但是
    递增数组的后面位置的值一定是大于当前位置的值。

    注意双端队列的常用方法：
     deque.isEmpty()    判断是否为空
     deque.peekLast()   查看队尾元素
     deque.peekFirst()  查看队首元素
     deque.pollFirst()  移除队首元素
     deque.pollLast()   移除队尾元素
     deque.offerFirst() 从队首添加元素
     deque.offerLast()  从队尾添加元素
* */

import java.util.Deque;
import java.util.LinkedList;

public class Solution {
    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        int[] ans =maxSlidingWindow(nums, k);
        for (int t : ans){
            System.out.println(t);
        }
    }
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length < k){
            return null;
        }
        int[] ans = new int[nums.length - k + 1];
        int flag = 0;
        // 双端队列
        Deque<Integer> deque = new LinkedList<>();
        // 先将前k个数字的最大值选出来
        for (int i = 0; i < k ; i ++){
            while (!deque.isEmpty() && nums[i] >=nums[deque.peekLast()]){
                deque.pollLast();
            }
            deque.offerLast(i);
        }
        // 将首个前k个字最大的数存在ans[0]中
        ans[flag ++] = nums[deque.peekFirst()];
        for (int i = k; i < nums.length; i ++){
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]){
                deque.pollLast();
            }
            deque.offerLast(i);
            // 如果首位最大的数不在队列中，那么就要出队
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1){
                deque.pollFirst();
            }
            // 找到第一个在队列中的数然后存入数组
            ans[flag ++] = nums[deque.peekFirst()];
        }
        return ans;
    }
}
